package com.lg.algorithm.collections.list.my;

import java.util.List;
import java.util.Random;

public class SingleList {

    static Random random = new Random();


    /**
     * 循环创建单向链表
     * 返头节点
     */
    public static SingleNode createSingleList(int size) {
        SingleNode indexNode = size < 1 ? null : new SingleNode(random.nextInt(10));
        SingleNode res = indexNode;
        for (int i = 1; i < size; i++) {
            indexNode.setNext(new SingleNode(random.nextInt(10)));
            indexNode = indexNode.getNext();
        }
        return res;
    }

    public static SingleNode createSingleList(List<Integer> numbers) {
        SingleNode indexNode = numbers.size() < 1 ? null : new SingleNode(numbers.get(0));
        SingleNode res = indexNode;
        for (int i = 1; i < numbers.size(); i++) {
            indexNode.setNext(new SingleNode(numbers.get(i)));
            indexNode = indexNode.getNext();
        }
        return res;
    }

    /**
     * 单链表翻转
     * 1 2 3 null
     * null 1 2 3
     */
    public static SingleNode reverse(SingleNode headNode){

        SingleNode nextNode = headNode;
        headNode = null;
        SingleNode tempNode = null;
        while (nextNode !=null) {
            tempNode = nextNode.getNext();
            nextNode.setNext(headNode);
            headNode = nextNode;
            nextNode = tempNode;
        }

        return headNode;
    }


    /**
     * 遍历
     *
     * @param singleNode
     */
    public static void printList(SingleNode singleNode) {
        while (singleNode != null) {
            System.out.print(singleNode.getValue());
            System.out.print(" ");
            singleNode = singleNode.getNext();
        }
        System.out.println();
    }

    /**
     * 输出一个单链表中所有的数的组合
     * 输入为一个单向链表  和  组合数字的个数
     * 例如1 2 3 4          2
     * 输出
     * 1 2
     * 1 3
     * 1 4
     * 2 3
     * 2 4
     * 3 4
     *
     * 123
     * 124
     * 134
     * 234
     *
     * 当处理完一个之数之后  这个数就不用管了  和后面的没有关系
     * 搞一个当前节点，然后后边使用滑动窗口
     *
     * 如果后面是多个数，那么他是有多种顺序的，所以这个循环不变式是变的  不对
     * todo
     */
    static void printCombination(SingleNode head, int size) {
        while (head != null) {
            SingleNode start = head.getNext();
            SingleNode end = start;
            for (int i = 1; i < size-1 && end != null; i++) {
                end = end.getNext();
            }
            SingleNode index = start;
            while (end != null) {
                System.out.print(head.getValue() + " ");

                index = start;
                for (int i = 1; i < size; i++) {
                    System.out.print(index.getValue() + " ");
                    index = index.getNext();
                }

                System.out.println();

                start = start.getNext();
                end = end.getNext();
            }
            head = head.getNext();
        }
    }

    /**
     * 1 2 3 4 5 6 7  3
     * 定义函数的作用 并向下递推
     *     选1 在2 3 4 5 6 7中选2
     *     不选1 在2 3 4 5 6 7中选3
     */
    static void printCombination2(List<Integer> numList,int size,List<Integer> selected) {

        if (numList == null) {
            return;
        }

        if (size == 0) {
            //todo
            for (Integer integer : selected) {
                System.out.print(integer + " ");
            }
            System.out.println();
            return;
        }

        if (numList.isEmpty()) {
            return;
        }

        //选1
        selected.add(numList.get(0));
        printCombination2(numList.subList(1,numList.size()),size -1,selected);


        //不选1
        List<Integer> sub = numList.subList(1, numList.size());
        selected.remove(selected.size() - 1);
        printCombination2(sub,size,selected);
    }


    /**
     * 删除链表中年为2 的节点
     */

}
